#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<unordered_map>
#include<algorithm>
#include<functional>
using namespace std;
int dx[8] = { 0,0,1,-1,-1,1,-1,1 }, dy[8] = { 1,-1,0,0,-1,-1,1,1 };
vector<int> pondSizes(vector<vector<int>>& land) {
	vector<int> ret;
	int m = land.size(), n = land[0].size();
	vector<vector<bool>> visited(m, vector<bool>(n, false));
	auto bfs = [&](int i,int j)
	{
		queue<pair<int,int>> q;
		q.push({ i,j });
		visited[i][j] = true;
		int path = 1;
		while (!q.empty())
		{
			auto [x1, y1] = q.front();
			q.pop();
			for (int k = 0; k < 8; k++)
			{
				int x2 = x1 + dx[k], y2 = y1 + dy[k];
				if (x2 >= 0 && x2 < m && y2 >= 0 && y2 < n && visited[x2][y2] == false
					&& land[x2][y2] == 0)
				{
					path++;
					visited[x2][y2] = true;
					q.push({ x2,y2 });
				}
			}
		}
		ret.push_back(path);
	};
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (land[i][j] == 0 && visited[i][j] == false)
				bfs(i, j);
		}
	}
	sort(ret.begin(), ret.end());
	return ret;
}

vector<string> findItinerary(vector<vector<string>>& tickets) {
	unordered_map<string, priority_queue<string, vector<string>, greater<string>>> hash;
	for (auto& v : tickets)
	{
		hash[v[0]].push(v[1]);
	}
	vector<string> ret;
	function<void(string)> dfs = [&](string s)
	{
		while (hash.count(s)&&hash[s].size()>0)
		{
			string tmp = hash[s].top();
			hash[s].pop();
			dfs(tmp);
		}
		ret.push_back(s);
	};
	dfs("JFK");
	reverse(ret.begin(), ret.end());
	return ret;
}